package org.lintcode_Close.Stage1_Easy_50.O6简单递归;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @Auther: qingle
 * @Date: 2024/8/20-21:50
 * @Description:
 * @version: 1.0
 */
public class 有效的括号序列{


	private static final Map<Character,Character> map = new HashMap<Character,Character>(){{
		put('{','}'); put('[',']'); put('(',')'); put('?','?');
	}};

	public boolean isValidParentheses(String s) {
		// write your code here
		if (s.length() > 0 && !map.containsKey(s.charAt(0))) return false;
		LinkedList<Character> stack = new LinkedList<Character>() {{ add('?');}};

		for(Character c: s.toCharArray()) {
			if(map.containsKey(c)) stack.addLast(c);
			else if(map.get(stack.removeLast()) != c) return false;
		}
		return stack.size()== 1;
	}
}
